package personal.learn.algorithm;

/**
 * Dijkstra的Java实现
 * 1.构建二维数组weight存储无向图，weight[i][j]表示节点i到节点j的权值，即节点i到节点j的距离(下文以dij表示)。
 * 2.构建数组shortpath，存储起始节点(0)到各节点最短距离，即d0j(j为所有节点),初始化shortpath[0] = 0，其他值为无穷大。
 * 3.构建数组visited，标记各节点是否已被扩展（假设0为为扩展，1为已扩展），初始化visited[0] = 1,其他值为零。
 * 4.迭代算法，遍历二维数组weight，选择离起始节点距离最短的未标记结点k，将d0k记录至shortpath，并将k标记为已扩展，
 * 通过k更新起始节点到其他各节点的距离，若d0j > d0k + dkj ，则d0j = d0k + dkj。
 * @author Chai yansheng
 * @create 2019/8/27
 **/
public class Dijkstra {
    public static final int MAX = Integer.MAX_VALUE;
    public static  int[] Dijsktra(int [][] weight,int start){
        int length = weight.length;// 获取顶点个数
        int[] shortPath = new int[length];// 最短路径数组
        shortPath[start] = 0; // 起点到自己的路径为0
        String[] path = new String[length];// 记录起始点到各定点的最短路径
        for(int i = 0 ; i < length ; i++){
            path[i] = start + "->" + i;
        }
        int[] visited = new int[length];//记录当前顶点的最短路径是否已经求出，1表示已求出
        for(int i = 0 ; i < length ; i++){
            visited[i] = 0;
        }
        visited[start] = 1;//起始点的最短路径已经求出
        for(int m = 1 ; m < length ; m ++){
            int k = -1;
            int dmin = MAX;

            // 选择一个离起始点最近的未标记顶点，且到起始点的最短路径为dmin
            for(int n = 0 ; n < length ; n++){
                if(visited[n] == 0 && weight[start][n] < dmin){
                    dmin = weight[start][n];
                    k = n;
                }
            }
            shortPath[k] = dmin;
            visited[k] = 1;
            //以k为中间点，更新起始点到其他未标记各点的距离
            for(int j = 0 ; j < length ; j++){
                if(visited[j] == 0 && weight[k][j] != MAX && weight[start][k] + weight[k][j] < weight[start][j]){
                    weight[start][j] = weight[start][k] + weight[k][j];
                    path[j] = path[k] + "->" + j;
                }
            }
        }
        for(int i = 1 ; i < length ; i ++){
            System.out.println("起始点" + start + "到" + i + "的最短路径为:" + path[i] + "距离为：" + shortPath[i]);
        }
        return shortPath;
    }
    public static int[] dijkstra(int [][]w, int start) {
        int length = w.length;
        int []path = new int[length];
        int []visit = new int[length];
        path[start] = 0;
        visit[start] = 1;
        for (int i = 0; i < length; i++) {
            int  k = -1, min = MAX;
            for (int j = 0; j < length; j++) {
                if (visit[j] == 0 && w[start][j] < min) {
                    min = w[start][j];
                    k = j;
                }
            }
            path[k] = min;
            visit[k] = 1;
            for (int j = 0; j < length; j++) {
                if (visit[j] == 0 && w[k][j] != MAX && w[start][k] + w[k][j] < w[start][k]) {
                    w[start][j] = w[start][k] + w[k][j];
                }
            }
        }
        return path;
    }
    public static void main(String[] args) {
        int[][] weigth = {
                {0, 50, 70, MAX, MAX},
                {50, 0, 15, 30, MAX},
                {70, 15, 0, MAX, 40},
                {MAX, 30, MAX, 0, 20},
                {MAX, MAX, 40, 20, 0}};

        Dijsktra(weigth,0);
    }
}
